package gold.digger;

import gold.utils.InputUtil;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC913 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 不愧是Hard难度，也是一道很有意思的题目
     * @return:
     * 方法、记忆化搜索
        今天这道题我们分情况来讨论即可。

        老鼠行动的结果从好到坏依次是：老鼠赢 > 平局 > 猫赢。

        猫行动的结果从好到坏依次是：猫赢 > 平局 > 老鼠赢。

        所以，我们的代码也可以从这两个大的维度来组织代码，然后，再分别对应三种小情况。

        另外，因为无向图可能存在环，猫可能一直都抓不到老鼠，老鼠也一直走不到洞里去，这种情况就是平局，我们不能让它们无限在里面玩，所以，最多 2n 次行动之后，如果无法确定输赢就是平局了。
     */
    class Solution {

        /**
         * 平局
         */
        private static final int DRAW = 0;
        /**
         * 老鼠赢
         */
        private static final int MOUSE_WIN = 1;
        /**
         * 猫赢
         */
        private static final int CAT_WIN = 2;

        public int catMouseGame(int[][] graph) {
            int n = graph.length;
            int[][][] memo = new int[n][n][2 * n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    Arrays.fill(memo[i][j], -1);
                }
            }
            return dfs(graph, n, memo, 2, 1, 0);
        }

        private int dfs(int[][] graph, int n, int[][][] memo, int catPos, int mousePos, int turns) {
            // 超过节点数两倍，可以确定为平局
            if (turns >= 2 * n) {
                return 0;
            }

            // 缓存中有，直接返回
            if (memo[catPos][mousePos][turns] != -1) {
                return memo[catPos][mousePos][turns];
            }

            // 老鼠赢
            if (mousePos == 0) {
                return memo[catPos][mousePos][turns] = MOUSE_WIN;
            }

            // 猫赢
            if (catPos == mousePos) {
                return memo[catPos][mousePos][turns] = CAT_WIN;
            }

            // turns 为偶数是轮到老鼠走，为奇数是轮到猫走
            if (turns % 2 == 0) {
                // 老鼠最坏情况是猫赢
                int ans = CAT_WIN;
                // 尝试走到下一个节点
                for (int nextPos : graph[mousePos]) {
                    int nextAns = dfs(graph, n, memo, catPos, nextPos, turns + 1);
                    // 如果老鼠可以赢，直接返回
                    if (nextAns == MOUSE_WIN) {
                        return memo[catPos][mousePos][turns] = MOUSE_WIN;
                    }
                    // 有平局，先记录为平局，后面如果有老鼠可以赢的场景，通过上述语句可以返回
                    if (nextAns == DRAW) {
                        ans = DRAW;
                    }
                }
                // 返回老鼠走的结果
                return memo[catPos][mousePos][turns] = ans;
            } else {
                // 猫最坏情况是老鼠赢
                int ans = MOUSE_WIN;
                for (int nextPos : graph[catPos]) {
                    // 注意猫不能走到0号节点
                    if (nextPos != 0) {
                        // 尝试进入下一个节点
                        int nextAns = dfs(graph, n, memo, nextPos, mousePos, turns + 1);
                        // 如果猫可以赢，直接返回
                        if (nextAns == CAT_WIN) {
                            return memo[catPos][mousePos][turns] = CAT_WIN;
                        }
                        // 有平局，先记录为平局，后面如果有猫可以赢的场景，通过上述语句可以返回
                        if (nextAns == DRAW) {
                            ans = DRAW;
                        }
                    }
                }
                // 返回猫走的结果
                return memo[catPos][mousePos][turns] = ans;
            }
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC913 an = new LC913();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
